package leetcode.hot100;

/**
 * leetcode: 轮转数组
 * 测试链接: https://leetcode.cn/problems/rotate-array/?envType=study-plan-v2&envId=top-100-liked
 *
 */
public class RotateArray {

    /**
     * 方法一：使用额外数组
     * @param nums
     * @param k
     */
//    public void rotate(int[] nums, int k) {
//        int len = nums.length;
//        int[] newNum = new int[len];
//        for(int i = 0; i < len; i++){
//            newNum[(i + k) % len] = nums[i];
//        }
//        System.arraycopy(newNum, 0, nums, 0, len);
//    }

    /**
     * 方法二：数组翻转
     * 数组可以分成两段 A+B，轮转之后要变成B+A
     *
     * 可以通过三次反转实现：
     * 1、先反转整个数组，得到reverse(B)+reverse(A)
     * 2、反转 reverse(B),reverse(reverse(B)) = B
     * 3、反转 reverse(A),reverse(reverse(A)) = A
     * @param nums
     * @param k
     */
    public void rotate(int[] nums, int k) {
        int len = nums.length;
        k %= len;
        reverse(nums, 0, len - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, len - 1);
    }

    public static void reverse(int[] nums, int l, int r){
        while(l < r){
            int tmp = nums[l];
            nums[l++] = nums[r];
            nums[r--] = tmp;
        }
    }
}
